var num = 0;
function inOrderSearch(arr, target) {
    for(var i = 0;i < arr.length ;i ++){
        num ++;
        if(arr[i] === target){
            return true;
        }
    }
    return false;
}

/**
 * 二分查找
 * @param arr
 * @param target
 * @returns {boolean}
 */
function binarySearch(arr, target) {
    if(arr.length === 0||target < arr[0] || target > arr[arr.length - 1]) return false;
    var minIndex = 0;
    var maxIndex = arr.length - 1;
    while(minIndex <= maxIndex){
        num ++;
        var mid = Math.floor((minIndex + maxIndex) / 2);
        if(arr[mid] == target){
            return true;
        }else if(arr[mid] > target){
            maxIndex = mid - 1;
        }else{
            minIndex = mid + 1;
        }
    }
    return false;
}


function interpolationSearch(arr,target) {
    if(arr.length === 0||target < arr[0] || target > arr[arr.length - 1]) return false;
    var minIndex = 0;
    var maxIndex = arr.length - 1;
    while(minIndex <= maxIndex){
        num ++;
        var mid = (target - arr[minIndex])/(arr[maxIndex] - arr[minIndex]) * (maxIndex - minIndex) + minIndex;
        if(arr[mid] === target){
            return true;
        }else if(arr[mid] > target){
            maxIndex = mid - 1;
        }else{
            minIndex = mid + 1;
        }
    }
    return false;
}
var arr = new Array(100000);
for(var i = 0; i < arr.length;i ++){
    arr[i] = i + 1;
}
// var result = inOrderSearch(arr, 500);

// var result = binarySearch(arr,50);

var result = interpolationSearch(arr,400);
console.log(result,num);
